"""
102. 二叉树的层序遍历
给你一个二叉树，请你返回其按 层序遍历 得到的节点值。 （即逐层地，从左到右访问所有节点）。

 

示例：
二叉树：[3,9,20,null,null,15,7],

    3
   / \
  9  20
    /  \
   15   7
返回其层序遍历结果：

[
  [3],
  [9,20],
  [15,7]
]
"""
try:
    from binarytree import Node as TreeNode
except:
    ...
finally:
    from queue import Queue
    from typing import List


class Solution:
    def levelOrder(self, root: TreeNode) -> List[List[int]]:
        ...
        if not root:
            return []

        current_nodes = Queue()
        # 0 denote the depth of root
        current_nodes.put(root)

        res = []

        while not current_nodes.empty():
            next_nodes = Queue()
            tmp_res = []
            while not current_nodes.empty():
                current_node = current_nodes.get()
                tmp_res.append(current_node.val)
                if current_node.left:
                    next_nodes.put(current_node.left)
                if current_node.right:
                    next_nodes.put(current_node.right)
            current_nodes = next_nodes
            res.append(tmp_res)
        return res


if __name__ == "__main__":
    from binarytree import tree

    my_tree = tree()
    print(my_tree)
    s = Solution()
    print(s.levelOrder(my_tree))
